package fun.coding.leetcode;

public class BinaryTreeMaximumPathSum {

	public static void main(String[] args) {

	}
	
	//    1
	//   2    -> 3
	
	// Could also pass in as a reference
	int max = Integer.MIN_VALUE;
	
	public int maxPathSum(TreeNode root) {
		maxPathSumHelper(root);
		return max;
	}
	
	public int maxPathSumHelper(TreeNode root) {
		if (root == null) return 0;
		
		int left = maxPathSumHelper(root.left);
		int right = maxPathSumHelper(root.right);
		
		// whether it is on the same side of tree
		int singlePath = Math.max(root.val, Math.max(left, right) + root.val);
		// Or across the current node on two sides
		int acrossPath = Math.max(singlePath, left + right + root.val);
		if (acrossPath > max) max = acrossPath;
		
		// always want to return the single path for recursion
		return singlePath;
    }

}
